/*
   FROM: http://www.newsmth.net/bbstcon.php?board=CPlusPlus&gid=321891

   发信人: fentoyal (fentoyal), 信区: CPlusPlus
   标  题: [技巧]任意维的连续空间数组的动态分配方法（模板）
   发信站: 水木社区 (Tue Apr 12 10:44:50 2011), 站内

   (谢谢ilovecpp的提醒，修改了下，不用返回那个丑陋的void *了)
   虽然这个时代各种容器横行，但是有时还是得要用数组，快啊。
   当然得要动态分配的，常见方法一般要么就将多维转成一维，算坐标换算，麻烦啊；
   要么就是先分配n个第一维，再用一个高维数组装这n个指针。但这样其实整个空间并不是连续的。

   心目中理想的三维数组分配器应该能达到类似这样静态分配的效果：
   int arr3d[4][5][6] = {0};
   这样分配出的空间的好处是,任意维都是连续的:
   arr3d[1][2][3] equals (*arr3d)[1*5 + 2][3] equals (**arr3d)[1*5*6 + 2*6 + 3]
   当然，想用动态分配达到这样的效果的方法也挺常见，就是代码很麻烦，而且只是针对某一维度，没有普适性。由于我经常要各种高维的数组，所以自己写了一个能分配任意维的理想数组的模板。代码包含分配和释放两个接口。其中分配有alloc 和 new 两种。 code有点长，主要思想是类模板的递归继承&实例化 及 模板的partial instantiation。
   如下：
 */

#include <stdlib.h>
#include <iostream>

#define PTRERR -1
#define GOOD 0

template< class ElemClass, size_t N_Dim >
class DynArrBuilder : public DynArrBuilder< ElemClass *, N_Dim - 1 > {
public:
	typedef typename DynArrBuilder< ElemClass *, N_Dim - 1 >::FinalType FinalType;
protected:

	static FinalType _bldCurDim( size_t sizec, size_t sizes[], ElemClass lower_dim )
	{
		size_t dim_size = 1;

		for( size_t i = 0; i < sizec; ++i )
			dim_size *= sizes[i];
		ElemClass *higher_dim = new ElemClass[dim_size];
		higher_dim[0] = lower_dim;
		for( size_t i = 1; i < dim_size; ++i )
			higher_dim[i] = higher_dim[i - 1] + sizes[sizec];
		return DynArrBuilder < ElemClass *, N_Dim - 1 >::_bldCurDim( sizec - 1, sizes, higher_dim );
	}
	static ElemClass _freeCurDim( FinalType ptr )
	{
		ElemClass *cur_ptr = DynArrBuilder < ElemClass *, N_Dim - 1 >::_freeCurDim( ptr );

		if( cur_ptr == NULL ) return NULL;
		ElemClass lower_ptr = *cur_ptr;
		delete [] (cur_ptr);
		return lower_ptr;
	}


public:

	static FinalType arrallocate( size_t sizes[] )
	{
		size_t dim_size = 1;

		for( size_t i = 0; i < N_Dim; ++i )
			dim_size *= sizes[i];

		ElemClass *base = reinterpret_cast < ElemClass * > (operator new ( dim_size * sizeof(ElemClass)));
		return DynArrBuilder < ElemClass *, N_Dim - 1 >::_bldCurDim( N_Dim - 1, sizes, base );
	}
	static FinalType arrnew( size_t sizes[] )
	{
		size_t dim_size = 1;

		for( size_t i = 0; i < N_Dim; ++i )
			dim_size *= sizes[i];
		ElemClass *base = new ElemClass[dim_size];
		return DynArrBuilder < ElemClass *, N_Dim - 1 >::_bldCurDim( N_Dim - 1, sizes, base );
	}
	static int arrfree( FinalType ptr )
	{
		if( ptr == NULL ) return PTRERR;
		ElemClass *cur_ptr = DynArrBuilder < ElemClass *, N_Dim - 1 >::_freeCurDim( ptr );
		if( cur_ptr == NULL ) return PTRERR;
		operator delete ( cur_ptr );
		return GOOD;
	}
	static int arrdelete( FinalType ptr )
	{
		if( ptr == NULL ) return PTRERR;
		ElemClass *cur_ptr = DynArrBuilder < ElemClass *, N_Dim - 1 >::_freeCurDim( ptr );
		if( cur_ptr == NULL ) return PTRERR;
		delete [] cur_ptr;
		return GOOD;
	}
};

template < class ElemClass >
class DynArrBuilder< ElemClass, 0 > {
protected:
	typedef ElemClass FinalType;
	static FinalType _bldCurDim( size_t sizec, size_t sizes[], ElemClass lower_base )
	{
		return lower_base;
	}
	static ElemClass _freeCurDim( FinalType ptr )
	{
		return ptr;
	}
};

#define PR( x ) std::cout << # x << ": " << (x) << std::endl;
int main( int argc, char *argv[] )
{
	size_t sizes[] = { 2, 3 };
	int **a = DynArrBuilder< int, 2 >::arrnew( sizes );

	a[0][1] = 10;

	PR( a[0][1] );

	DynArrBuilder< int, 2 >::arrdelete( a );
}

/*

   USAGE：
   size_t sizes[] = {2,3,3,3}; //2 is the highest dimension.
   MyClass **** my_classes = DynArrBuilder<MyClass, 4>::arrnew(sizes) ;
   DynArrBuilder<MyClass, 4>::arrdelete(my_classes);

   BT USAGE：//分配一个10000维数组，每维度大小等于当前维数
   size_t sizes[10000];
   for (int i = 0; i < 10000; ++i)
   sizes[i] = 10000 - i;
   DynArrBuilder<MyClass, 10000>::FinalType my_classes = DynArrBuilder<MyClass, 10000>::arrnew(sizes) ;
   DynArrBuilder<MyClass, 10000>::arrdelete(my_classes);

 */


/*

   主要的逻辑就是
   首先, 分配整个的容纳数据的空间。
   然后，通过模板类的递归实例化，实现一层一层建立容纳低级数组指针的高一级的数组
   最后，最下面的那个模板就是递归实例化的结束条件。
   Note1： 用类模板的原因是，函数模板不支持partial instantiation，就无法实现递归实例化。
   Note2：谢谢ilovecpp同学的提醒，用typedef的话，就可以提前确定返回类型有几颗*（多少维指针）
   Note3: 异常是能一级一级的抛到最外面的
   Note4： 继承是想照顾下protect里那俩函数，不用继承都public也是可以的。
   --
 */
